/* permutations      GCW      11/01/95   

   This uses and displays the following algorithm for
   running through permutations from 0 1 ... n to
   n ... 1 0.  
   Step 1. Starting from the right hand end, find the
           first element smaller than its right hand 
           neighbour - call it fred. Then find the
           next largest number to the right of fred,
           call it sam.
   Step 2. Swap fred and sam.
   Step 3. Reverse the list of numbers to the right
           of fred's old position.

  This program shows the intermediate steps, underlining
  the pair (fred,sam).
*/
 
main()
{
 do
 {
  print("Input a smallish number (2-7): ");
  n = val(input());
 } 
 until (n < 8 && n > 1);
 v = newvector(n);
 fact = 1;
 for ( k = n; k > 0;)
 {
  fact *= k--;
  v[k] = k;
 }
 print("> ");
 display(v);
 newline();
 for (k = 1; k < fact; k++)
  permute(v);
}

display(v)
{
 local i,n;
 n = sizeof(v);
 for ( i = 0; i < n; i++)
  print(v[i]," ");
}

newline()
{ print("\n"); }

permute(v)
{
 local n,fred,sam;
 n = sizeof(v);
 sam = n-1;
 fred = sam-1;
 while (v[fred] > v[fred+1] && fred > 0) fred--;
 while (v[sam] < v[fred] && sam > fred) sam--;
 underline(fred,sam,n);
 swap(v,fred,sam);
 display(v);
 reverse(v,fred+1);
 print("    reverse\n> ");
 display(v);
 newline();
}

reverse(v,k)
{
 local n,i,half,offset;
 n = sizeof(v);
 half = (n+k)/2;
 offset = n+k-1;
 for (i = k; i < half; i++)
   swap(v,i,offset-i);
}

swap(v,i,j)
{
 local w;
 w = v[i];
 v[i] = v[j];
 v[j] = w;
}

underline(i,j,n)
{
 local k;
 print("  ");
 for(k = 0; k < n; k++)
    print(((k == i)||(k == j))?"^ ":"  ");
 print("    swap\n  ");
}
